package 二分;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/26 12:24
 */
public class leetcode6357使数组相等最小操作 {
    /*
     这种 使数组 相等的最小操作,  这类问题出现的频率很高!


     == 这个题的一个核心点,在于
     < queries[index]的 要执行 加操作, 而 > queries[index] 的要执行 减操作

     前缀和 + 二分 !
     */

/*
这个题  的 int 溢出! 卧槽, 卡了好久!

以及 特殊的 case , 比如 queries[index] < min(nums[i]) || queries[index] > max(nums[i]) 这种情况的 时候, 二分 的问题, (这种 问题, 之前就思考过!)
 */
    public List<Long> minOperations(int[] nums,  int[] queries) {
        List<Long> ans = new ArrayList<>(queries.length);
        long preSum[] = new long [nums.length + 1];
        //  sort
        Arrays.sort(nums);
        for(int i = 0;i < nums.length;i++){
            preSum[i + 1] = preSum[i] + nums[i];
        }
        int index = 0;
        while(index < queries.length){
            if(queries[index] < nums[0] || queries[index] > nums[nums.length - 1]){
                ans.add((long)Math.abs(preSum[nums.length] - (long)queries[index] * nums.length));
                index++;
                continue;
            }
            int l = binarySearch(nums,queries[index]);
            long leftOp = (long)(l + 1) * queries[index]  - preSum[l + 1];
            long rightOp = preSum[nums.length] - preSum[l + 1] - (long)(nums.length - l - 1) * queries[index];
            ans.add(leftOp + rightOp);
            index++;
        }
        return ans;
    }
    public int binarySearch(int nums[],int aim){
        int l = 0, r = nums.length - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] > aim){
                r = mid - 1;
            }else{
                l = mid;
            }
        }
        return l;
    }

    @Test
    public void test(){
//        int nums[] = {3,1,6,8};
//        int queries[] = {1,5};
//        System.out.println(minOperations(nums,queries));
        int arr1[] = {607,855,747,655,633,825,943,905,633,1227,685,1009,675,805,905,1323,655,625,619,607,929,605,1179,611,685,653,833,639,949,819,689,851,759,699,639,655,855,661,605,833,855,869,783,655,1097,839,1009,1179,1031,855,721,679,723,783,697,685,833,833,655,833};
        int arr2[] = {607,855,747,655,633,825,943,905,633,1227,685,1009,675,805,905,1331,655,625,619,607,929,605,1179,611,685,653,833,639,949,819,689,851,759,699,639,655,855,661,605,833,855,869,783,655,1097,839,1009,1179,1031,855,721,679,723,783,697,685,833,833,655,833};
//        System.out.println(Arrays.equals(arr1,arr2));
        for(int i = 0;i < arr1.length;i++){
            if(arr1[i] != arr2[i]){
                System.out.println(i + " " + arr1[i] + "  " + arr2[i]);
            }
        }
    }
}
